#include "cdsl.h"

void xchg_node(struct tree_node *n1, struct tree_node *n2)
{
    struct tree_node **p1, **p2, *lc1, *rc1, *lc2, *rc2;

    /* Setup external links */
    p1 = is_root(n1) ? NULL :
      is_child_left(n1) ? &n1->pn->lc : &n1->pn->rc;
    p2 = is_root(n2) ? NULL :
      is_child_left(n2) ? &n2->pn->lc : &n2->pn->rc;

    lc1 = left(n1);
    rc1 = right(n1);
    lc2 = left(n2);
    rc2 = right(n2);

    if (!is_root(n1)) {
        *p1 = n2;
    }
    if (!is_root(n2)) {
        *p2  = n1;
    }
    if (!is_leaf(lc1)) { 
        set_parent(lc1, n2);
    }
    if (!is_leaf(rc1)) { 
        set_parent(rc1, n2);
    }
    if (!is_leaf(lc2)) { 
        set_parent(lc2, n1);
    }
    if (!is_leaf(rc2)) { 
        set_parent(rc2, n1);
    }

    /* Exchange node links */
    xchg(n1->lc, n2->lc);
    xchg(n1->rc, n2->rc);
    xchg(n1->pn, n2->pn);

    /* Handle special cases when the nodes are linked */
    if (n1->pn == n2) {
        if (n2->rc == n2) {
            /* Case 1: n1->rc = n2 */
            n2->rc = n1;
            n1->rc = rc2;
        }
        else if (n2->lc == n2) {
            /* Case 2: n1->lc = n2 */
            n2->lc = n1;
            n1->lc = lc2;
        }
    }
    else if (n2->pn == n1) {
        if (n1->rc == n1) {
            /* Case 1: n2->rc = n1 */
            n1->rc = n2;
            n2->rc = rc1;
        }
        else if (n1->lc == n1) {
            /* Case 2: n2->lc = n1 */
            n1->lc = n2;
            n2->lc = lc1;
        }
    }
}
